/*
	class fwtree2:
		2d fenwick tree, (c) marqueewinq, 2012
	using _Ty requires:
		default constructor: _Ty(0) 
		operator + (_Ty a, _Ty b)
*/

#define _Ty long long
class fwtree2
{
public:
	void init(vector <vector <_Ty> > &base);
	void inc(int x, int y, _Ty delta);
	_Ty rsq(int x1, int y1, int x2, int y2);
private:
	vector <vector <_Ty> > tree;
	_Ty sum(int x, int y);
};

void fwtree2::init(vector <vector <_Ty> > &base)
{
	tree.clear();
	if (base.size() != 0)
		tree.resize(base.size(), vector <_Ty> (base.front().size()));
	for (int i = 0; i < base.size(); i++)
		for (int j = 0; j < base[i].size(); j++)
			inc(i, j, base);
}

void fwtree2::inc(int x, int y, _Ty delta)
{
	for (int i = x; i < tree.size(); i = i | (i + 1))
		for (int j = y; j < tree.size(); j = j | (j + 1))
			tree[i][j] = tree[i][j] + delta;
}

_Ty fwtree2::rsq(int x1, int y1, int x2, int y2)
{
	return sum(x2, y2) - sum(x2, y1 - 1) - sum(x1 - 1, y2) + sum(x1 - 1, y1 - 1);
}

_Ty fwtree2::sum(int x, int y)
{
	_Ty r(0);
	for (int i = x; i >= 0; i = i & (i + 1) - 1)
		for (int j = y; j >= 0; j = j & (j + 1) - 1)
			r = r + tree[i][j];
	return r;
}